/**
 * @file     heapSort.js
 * @brief    堆排序
 * @author   Zhu
 * @date     2023-06-01 06:12
 */

class MinHeap {
    constructor(arr = []) {
        this.arr = arr;
    }

    size() {
        return this.arr.length;
    }

    hasLeft(i) {
        return 2 * i + 1 < this.arr.length;
    }
    hasRight(i) {
        return 2 * i + 2 < this.arr.length;
    }
    hasParent(i) {
        return Math.floor((i - 1) / 2) >= 0;
    }

    left(i) {
        return 2 * i + 1;
    }
    right(i) {
        return 2 * i + 2;
    }
    parent(i) {
        return Math.floor((i - 1) / 2);
    }

    swap(i, j) {
        const temp = this.arr[i];
        this.arr[i] = this.arr[j];
        this.arr[j] = temp;
    }

    heapifyUp(i = this.arr.length - 1) {
        while (
            this.hasParent(i) &&
            // comp
            this.arr[this.parent(i)] > this.arr[i]
        ) {
            this.swap(this.parent(i), i);
            i = this.parent(i);
        }
    }

    heapifyDown(i = 0) {
        while (this.hasLeft(i)) {
            let next = this.left(i);
            if (this.hasRight(i)) {
                // comp
                if (this.arr[this.left(i)] > this.arr[this.right(i)]) {
                    next = this.right(i);
                }
            }
            // comp
            if (this.arr[i] > this.arr[next]) {
                this.swap(next, i);
                i = next;
            } else {
                break;
            }
        }
    }

    add(e) {
        this.arr.push(e);
        this.heapifyUp();
    }

    poll() {
        if (this.arr.length === 0) return null;
        if (this.arr.length === 1) return this.arr.pop();

        const item = this.arr[0];
        this.arr[0] = this.arr.pop();
        this.heapifyDown();

        return item;
    }

    level(i) {
        let n = 0;
        let temp = i + 1;
        while ((temp = temp >> 1)) {
            n++;
        }
        return n;
    }

    print() {
        const size = this.size();
        let level = 1;
        let levelArr = [];
        for (let i = 0; i < size; i++) {
            if (2 ** level - 1 === i) {
                console.log(levelArr.join(' '));
                levelArr = [];
                level++;
            }
            levelArr.push(this.arr[i]);
        }
    }
}

function main() {
    const arr = [
        3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5,
        9, 7, 4, 0, 2, 6,
    ];

    const heap = new MinHeap();
    for (const item of arr) {
        heap.add(item);
    }

    console.log(heap.arr);
    heap.print();

    const sorted = [];
    while (heap.size()) {
        sorted.push(heap.poll());
    }

    console.log(sorted);
}

main();
